/*
   @Copyright:LeetCode
   @Author:   tjyemail
   @Problem:  http://leetcode.com/problems/sudoku-solver
   @Language: C++
   @Datetime: 19-06-05 16:42
   */

class Solution {
	bool valid(vector<vector<char> > &board, int row, int col, const char ch){
		for(int i=0; i<9; ++i){
			if(i!=col && board[row][i]==ch) return false;
			if(i!=row && board[i][col]==ch) return false;
			const int r=row/3*3+i/3, c=col/3*3+i%3;
			if((r!=row || c!=col) && board[r][c]==ch) return false;
		}
		return true;
	}
	bool solve(vector<vector<char> >& board, vector<pair<int,int> > &place, int n) {
		if(place.size()==n) return true;
		int row=place[n].first, col=place[n].second;
		for(char ch='1'; ch<='9'; ++ch){
			if(!valid(board,row,col,ch)) continue;
			board[row][col]=ch;
			if(solve(board,place,n+1)) return true;
			board[row][col]='.';
		}
		return false;
	}
public:
	void solveSudoku(vector<vector<char> >& board) {
		vector<pair<int,int> > place;
		for(int i=0; i<board.size(); ++i)
			for(int j=0; j<board[i].size(); ++j)
				if(board[i][j]=='.') place.push_back({i,j});
		solve(board,place,0);
	}
};
